package com.zhugang.week07;

/**
 * @program algorithms
 * @description: verifyPostorder
 * @author: chanzhugang
 * @create: 2022/07/28 11:06
 */
public class VerifyPostorder {

    /**
     * 剑指offer 33 二叉搜索树的后序遍历序列
     *
     * @param postorder
     * @return
     */
    public boolean verifyPostorder(int[] postorder) {
        // 左右子树是BST
        return myVerify(postorder, 0, postorder.length - 1);
    }

    private boolean myVerify(int[] postorder, int i, int j) {
        if (i >= j) {
            return true;
        }
        // postorder[j]是根节点， 先分离左子树[i, k - 1]
        int k = i;
        while (k < j && postorder[k] < postorder[j]) {
            k++;
        }

        int p = k;
        while (p < j) {
            // 验证[k, j - 1] 满足右子树的要求，都大于postorder[j]
            if (postorder[p] < postorder[j]) {
                return false;
            }
            p++;
        }


        boolean leftValid = myVerify(postorder, i, k - 1);
        if (!leftValid) {
            // 提前退出
            return false;
        }
        boolean rightValid = myVerify(postorder, k, j - 1);
        return rightValid;
    }
}